#include "Juego.h"
#include <cstdlib>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <list>
#include <map>
#include <climits>

using namespace std;

    
map <string,Juego*> mapjuegos;
Juego*** matrix;
int subjuegos;

void jugar(Juego * estado){
	int length = estado->end - estado->start ;
	int in_start = estado->start;
	int in_end = estado->end-1;
	int lado=0;
	int maxdiff = INT_MIN;
	int maxi;
	if (estado->turno != estado->actual){
		estado->cambiarJugadorActual();
		jugar(estado);
		if (!estado->finalizo()){
			jugar(estado);
			estado->turnoCount += 1 ;
		}
		return;
	}
	if ( matrix[in_start][in_end]  != NULL ){
		//printf("3.1\n");
		if (estado->actual != ((Juego*)matrix[in_start][in_end])->actual){
			*estado =  *(((Juego*)matrix[in_start][in_end]));
			estado->swapScores();	
		}else{
			*estado =  *(((Juego*)matrix[in_start][in_end]));
		}
		return;
	}
	if (length == 1){
		subjuegos += 1;
		int v = 0;		
		estado->addPuntos(estado->sum(1,0));
		estado->extraer(1);
		estado->turnoCount = 1;
		estado->pushMove(0,1);		
		matrix[in_start][in_end] = new Juego(estado);		
		return;
	}
	Juego * maxdiffJuego = new Juego();
	Juego * juegoderecha = new Juego();
	Juego * juegoizquierda = new Juego();

	int miJugador = estado->actual;
	int diffizq,diffder;
	int sumIzq=0;
	int sumDer=0;
	//
	for(int i=1; i<= length ; i++){
		*juegoizquierda = *estado;
		sumIzq = estado->sum(i,sumIzq);
		juegoizquierda->extraer(i);
		juegoizquierda->pasarTurno();
		if (i != length)
			jugar(juegoizquierda);
		//
		*juegoderecha = *estado;
		sumDer = estado->sum(-i,sumDer);
		juegoderecha->extraer(-i);
		juegoderecha->pasarTurno();
		if (i != length)
			jugar(juegoderecha);
		//
		juegoizquierda->cambiarJugadorActual(miJugador);
		diffizq = sumIzq + juegoizquierda->getPuntos() - juegoizquierda->getPuntosOtro(); 
		//
		juegoderecha->cambiarJugadorActual(miJugador);
		diffder = sumDer + juegoderecha->getPuntos() - juegoderecha->getPuntosOtro();
		//
		if (maxdiff == INT_MAX or maxdiff < diffizq or maxdiff < diffder ){
			maxi = i;
			if (diffizq >= diffder){
				maxdiff = diffizq;
				lado = 0;
				*maxdiffJuego = *juegoizquierda;
				maxdiffJuego->addPuntos(sumIzq);
			}else{
				lado = 1;
				maxdiff = diffder;
				*maxdiffJuego = *juegoderecha;				
				maxdiffJuego->addPuntos(sumDer);
			}
		}
	}
	subjuegos += 1;
	*estado = *maxdiffJuego;
	estado->cambiarJugadorActual(miJugador);
	estado->turnoCount += 1 ;
	estado->pushMove(lado,maxi);
	(matrix[in_start][in_end]) = new Juego(estado);		
}	 



int main(int argc, char** argv) {
	char line[1000];
	int length = -1;
	vector<int> v;
	subjuegos = 0;
	while ( cin.getline(line,50,' ') && line != "0" ){
		if(length == -1 ){
			length = atoi(line);
			v.resize(length);
			length = 0;
		}else{
			v[length] = atoi(line);
			length ++;
		}
	}
	
	length = v.size();	

	matrix = new Juego**[length];
	// printf("length %d \n",length);
	for (int i = 0; i < length; ++i){
		matrix[i] = new Juego*[length];
		for (int j=0; j< length-i ; j++)
			matrix[i][j]  = NULL;

	}
    		


	Juego* j = new Juego(&v);
	jugar(j);
		
	for (int i = 0; i < length; ++i)
    		delete [] matrix[i];
	delete [] matrix;
	
	cout  << *j;
	printf("Subjuegos %d %d\n",length,subjuegos);
    return 0;
}


